package LeetCodeTest.PrimaryAlgorithmTest.Array;

public class Rotate {
    /**
     * 给定一个 n×n 的二维矩阵matrix 表示一个图像。请你将图像顺时针旋转 90 度。
     * 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
     *
     * 示例 1：
     * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
     * 输出：[[7,4,1],[8,5,2],[9,6,3]]
     *
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnhhkv/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param args
     *
     * 思路：先沿对角线翻折，再沿竖直轴线翻折
     */

    public static void main(String[] args) {
        int[][] matrix = {{1,2,3},{4,5,6},{7,8,9}};
        Rotate rotate = new Rotate();
        rotate.rotate(matrix);
    }

    /**
     * 将四个边由外向内旋转
     * 1 2 3      7 2 1         7 4 1
     * 4 5 6  ->  4 5 6    ->   8 5 2
     * 7 8 9      9 8 3         9 6 3
     * @param matrix
     */
    public void rotate(int[][] matrix) {
        int length = matrix.length;
        //因为是对称的，只需要计算循环前半行即可
        for (int i = 0; i < length / 2; i++)
            for (int j = i; j < length - i - 1; j++) {
                int temp = matrix[i][j];
                int m = length - j - 1;
                int n = length - i - 1;
                matrix[i][j] = matrix[m][i];
                matrix[m][i] = matrix[n][m];
                matrix[n][m] = matrix[j][n];
                matrix[j][n] = temp;
            }
    }

    /**
     * 更改数组
     *  1 | 2 | 3      7 4 1         7 4 1       7 4 1
     *  4 | 5 | 6  ->  4 5 6    ->   8 5 2   ->  8 5 2
     *  7 | 8 | 9      7 8 3         7 8 3       9 6 3
     *  时间复杂度 O(2N) 空间复杂度 O(2N)不推荐
     */

    /**
     * 沿对角线翻转，再沿竖直轴线翻转
     * 时间复杂度O(2N)
     */
}
